class Solution
{
public:
    int waysToReachStair(int k)
    {
        unordered_map<long long, int> m;

        function<int(long long, long long, bool)> f = [&](long long cur, long long j, bool canDown)
        {
            long long state = ((long long)canDown << 61) + (j << 48) + cur;
            if (m.count(state))
            {
                return m[state];
            }

            int result = 0;
            if (cur == k)
            {
                result = 1;
            }
            if (cur > 0 && canDown)
            {
                result += f(cur - 1, j, false);
            }

            if (cur <= k + 1)
            {
                result += f(cur + (1 << j), j + 1, true);
            }

            m[state] = result;

            return result;
        };
        return f(1, 0, true);
    }
};